import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                ", random=" + random +
                '}';
    }
}

public class copyRandomListBak {

    Map<Node,Node> cachedNode = new HashMap<Node,Node>();

    /**
     * 拿到head节点在HashMap中对应的值
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        if(!cachedNode.containsKey(head))
        {
            //创建该节点
            Node headNew = new Node(head.val);
            //一创建就放入HashMap中,这样后续的递归操作才能拿到它
            cachedNode.put(head,headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        //如果HashMap中，已有了直接返回即可。
        return cachedNode.get(head);
    }

    public static void main(String[] args) {

    }
}
